package com.leetcode.algorithm.y22.m09.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 1080. 根到叶路径上的不足节点
 * 
 * https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/
 * 
 * @author jie.deng
 *
 */
class Question1088Solution01 {

	public TreeNode sufficientSubset(TreeNode root, int limit) {
		// DFS
		// 后序遍历
		if (root == null) {
			return root;
		}
		boolean isLeaf = (root.left == null && root.right == null);
		root.left = sufficientSubset(root.left, limit - root.val);
		root.right = sufficientSubset(root.right, limit - root.val);
		if (root.left == null && root.right == null) {
			if (!isLeaf || (isLeaf && root.val < limit)) {
				return null;
			}
		}
		return root;
	}

}